package com.zsj.Recursion;

import java.util.Arrays;
import java.util.Random;

/**
 * 程序员节日快乐
 *
 * @Author zsj
 * @Version 1.0
 * @Date 2023/10/24 14:26
 * @Description 阶乘问题
 */
public class Factorial {
    public static void main(String[] args) {
        int[] rr = new int[10000];
        initArr10000(rr);
//        System.out.println(System.currentTimeMillis());
//        bubbleSort(rr);
//        System.out.println(System.currentTimeMillis());
////        System.out.println(Arrays.toString(rr));

        int [] t = {2,1,35,6,8,1,2};
        insertSort(t);
        System.out.println(Arrays.toString(t));

    }

    private static void initArr10000(int[] rr) {
        for (int i = 0; i < rr.length; i++) {
            rr[i] = new Random().nextInt();
        }
    }

    /**
     * 阶乘
     *
     * @param num 几的阶乘
     * @return 阶乘结果
     */
    public static long getNumber(int num) {
        if (num == 1) return 1;
        return num * getNumber(num - 1);
    }

    /**
     * 逆向打印字符串
     *
     * @param str   字符
     * @param index 字符长度
     */
    public static void reversePrintStr(String str, int index) {
        if (index == 0) return;
        System.out.print(str.charAt(index - 1));
        reversePrintStr(str, index - 1);
    }

    public static void reversePrintStr2(String str, int index) {
        if (index == str.length()) return;
        // 这里写成index++  不知道为什么不可以
        reversePrintStr2(str, index + 1);
        System.out.print(str.charAt(index));
    }

    /**
     * 二分查找
     *
     * @param arr    数组
     * @param target 有序数组
     * @return 返回target下标 没找到返回-1
     */
    public static int binarySearch(int[] arr, int target) {
        return binarySearch(arr, target, 0, arr.length);
    }

    /**
     * 二分查找
     *
     * @return 找到对应下标
     */
    private static int binarySearch(int[] arr, int target, int left, int right) {
        if (left > right) return -1;
        int mid = (left + right) >> 1;
        if (target < arr[mid]) {
            //在左边
            return binarySearch(arr, target, left, mid - 1);
        } else if (target > arr[mid]) {
            return binarySearch(arr, target, mid + 1, right);
        } else return mid;

    }


    /**
     * 递归实现冒泡排序
     *
     * @param arr 传入数组
     */
    private static void bubbleSort(int[] arr) {
        bubble(arr, arr.length - 1);
    }

    /**
     * 将数组中最大元素移到max位置的最右边
     *
     * @param arr 数组
     * @param max 指定数组位置
     */
    private static void bubble(int[] arr, int max) {
        int x = 0;
        for (int i = 0; i < max; i++) {
            if (arr[i] > arr[i + 1]) {
                int t = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = t;
                x = i;
            }
        }
        if (max != 0) bubble(arr, x);
    }

    /**
     * 插入排序
     */
    private static void insertSort(int[] arr) {
        insertion(arr, 1);
    }

    /**
     * @param arr 传入排序数组
     * @param low 下边界
     */
    private static void insertion(int[] arr, int low) {
        if (low == arr.length) return;
        int t = arr[low];//
        int i = low - 1;//已经排序区域的指针

        while (i >= 0 && arr[i] > t) {
            arr[i + 1] = arr[i];
            i--;
        }
        arr[i + 1] = t;
        insertion(arr, low + 1);
    }



}

